import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-11-21
 * Time: 17:11
 */
//集合类型
/*
public classs Interval {
    int start, end;
    Interval(int start, int end){
        this.start = start;this.end = end;
    }
}

public class Solution {
    public int eraseOverlapIntervals(List<Interval> intervals) {
        // write your code here
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.end - b.end;
            }
        });
        int count = 1;
        int end = intervals.get(0).end;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals.get(i).start >= end) {
                count++;
                end = intervals.get(i).end;
            }
        }
        return intervals.size() - count;
    }
}

 */
//数组类型
class myComparator implements Comparator<int[]>{
    @Override
    public int compare(int[] o1, int[] o2) {
        return o1[1]-o2[1];
    }
}
public class NonOverlapping {
    public static int eraseOverlapIntervals(int[][] intervals) {
        int num=1;
        int i=0;
        if(intervals.length==0){
            return -1;
        }
        Arrays.sort(intervals,new myComparator());
        for(int j=1;j<intervals.length;++j){
            if(intervals[j][0]>=intervals[i][1]){
                ++num;
                i=j;
            }
        }
        return intervals.length-num;//反着来，跟那个活动安排问题相反，用总的个数减去不重叠的区间个数
    }

    public static void main(String[] args) {
        int[][] intervals={{1,2}, {2,3}, {3,4}, {1,3} };
        System.out.println("需要删除的区间个数是"+eraseOverlapIntervals(intervals));
    }
}
